package Stack;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Stack
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-21  14:23
 * @Description: TODO
 * @Version: 1.0
 */
public class 下一个更大元素III556 {

    public int nextGreaterElement(int n) {
        char[] nums = Integer.toString(n).toCharArray();
        int i=nums.length-2;
        // 从后向前找到的一个降序排列的数据
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 如果都是升序的 那就不存在这样的一个数字
        if (i < 0) {
            return -1;
        }
        int j = nums.length - 1;
        // 从后向前找到第一个比nums[i]小的值 然后交换他们
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        // 交换当前的两个元素
        swap(nums, i, j);
        // 然后在将i+1 end的进行的反转
        reverse(nums, i + 1,nums.length-1);
        long ans = Long.parseLong(new String(nums));
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }

    // 反转i+i end元素
    public void reverse(char[] nums, int begin,int end) {
        while (begin<=end){
            Character c=nums[begin];
            nums[begin]=nums[end];
            nums[end]=c;
            begin++;
            end--;
        }
    }

    // 交换两个元素
    public void swap(char[] nums, int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
